# 4. 地上有一个m行n列的方格,从坐标[0, 0]到坐标[m-1, n-1].
# 一个机器人从坐标[0, 0]的格子开始移动,他每次可以向左/右/上/下移动1格(不能移动到方格区域外),
# 也不能进入行坐标和列坐标的各数位数字之和大于k的格子,例如,当k为18时,机器人能够进入方格[35, 37],
# 因为3+5+3+7=18,但它不能进入[35, 38]的格子,因为3+5+3+8=19,请问该机器人能够到达多少个格子?
# 示例:
# 输入: m=2, n=3, k=1
# 输出: 3
# 提示:
#   1<=n,m<=100
#   0<=k<=20


class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:
        vis = set([(0, 0)])
        for i in range(m):
            for j in range(n):
                if ((i - 1, j) in vis or (i, j - 1) in vis) and digit_sum(i) + digit_sum(j) <= k:
                    vis.add((i, j))
        print(len(vis))
        return len(vis)


def digit_sum(num):
    ans = 0
    while num:
        ans += num % 10
        num //= 10
    return ans


if __name__ == '__main__':
    s = Solution()
    s.movingCount(38, 15, 10)


